package puzzle.projecteuler.p100;

import java.util.List;

import astudy.util.AdvMath.Factors;

public class Problem075 {

	/**
	 *    a^2 + b^2 = c^2 = (L-a-b)^2
	 * => 0 = L^2 + 2ab - 2aL - 2bL
	 * 
	 * so, if L is odd, return 0;
	 * else, L is even, L = 2t
	 * =>  0 = 2*t^2 + ab - 2at - 2bt
	 * =>  (2t-a)*(2t-b) = 2t^2 
	 * 
	 * 注： 程序运行了147781 ms，很慢。
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		
		long s = System.currentTimeMillis();
		int m = 2000000;
		int c = 0;
		for (int L = 1; L <= m; L ++) {
			if (count(L) == 1) c ++;
		}
		System.out.println(c);
		System.out.println((System.currentTimeMillis()-s) + " ms");
	}
	
	public static int count(int L) {
		if (L%2 == 1) {
			return 0;
		} else {
			int t = L/2;
			Factors f = new Factors(t);
			f = new Factors(2).merge(f).merge(f);
			List<Factors> fs = f.getAllFactors();
			int c = 0;
			for (int i = 0; i < fs.size()/2; i ++) {
				if (fs.get(i).longValue() < L && fs.get(fs.size()-i-1).longValue() < L) {
					c ++;
				}
			}
			return c;
		}
	}

}
